/**
 * Consider the divisors of 30: 1,2,3,5,6,10,15,30.
 * It can be seen that for every divisor d of 30, d+30/d is prime. 
 *
 * Find the sum of all positive integers n not exceeding 100 000 000
 * such that for every divisor d of n, d+n/d is prime. 
 */

#include <iostream>
#include "euler/prime_table.hpp"
#include "euler/divisor.hpp"
#include "euler.h"

BEGIN_PROBLEM(357, solve_problem_357)
	PROBLEM_TITLE("Prime generating integers")
	PROBLEM_ANSWER("1739023853137")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("N^1.5/ln(N)")
	PROBLEM_SPACE_COMPLEXITY("N")
END_PROBLEM()

static void solve_problem_357()
{
#if 0
	const int N = 100; // 401
	//const int N = 1000000000; // 50,847,534 primes
#else
	const int N = 100000000; // 5,761,455 primes
#endif

	bool verbose = false;
	long long sum = 0;
	euler::prime_table<int> primes(N);

	std::for_each(primes.begin(), primes.end(), [&](int n) {
		--n;
#if 1
		for (int k = 2; k*k <= n; k++)
		{
			if (n % k == 0)
			{
				int d = n / k;
				if (!primes.test(d+k))
					return;
				if (primes.test(d)) // no more unchecked divisors
					break;
			}
		}
#else
		if (!std::all_of(euler::divisor_iterator<int>(n), euler::divisor_iterator<int>(), 
			[&](int d) -> bool { return primes.test(n/d+d); }))
			return;
#endif
		if (verbose)
			std::cout << n << std::endl;
		sum += n;
	});

	std::cout << sum << std::endl;
}
